package Algorithm.Dp;
//https://leetcode-cn.com/problems/longest-increasing-subsequence/
public class Leetcode300 {
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int len = 1, n = nums.length;
            if(n==0)
                return 0;

            int[] d = new int[n+1];
            d[len] = nums[0];
            for(int i=1;i<n;i++){
                if(nums[i]>d[len]){
                    d[++len] = nums[i];
                }else{
                    // 二分查找
                    int l=1, r = len;
                    while(l<r){
                        int mid = (l+r)/2;
                        if(nums[i]==d[mid]){
                            break;
                        }else if(nums[i]>d[mid]){
                            l = mid + 1 ;
                        }else{
                            r = mid ;//因为需要把大的值替换为小的值，所以不能写成 r = mid-1,而是写成 r = mid，这样当 l==r 的时候，直接替换就行
                        }
                    }

                    if(l==r){
                        d[l] = nums[i];
                    }
                }
            }

            return len;

        }
    }
}
